package com.sheng.leetcode.year2024.month01.day03;

import org.junit.Test;

import java.util.Stack;

/**
 * @author by ls
 * @date 2024/1/3
 * <p>
 * 2487. 从链表中移除节点<p>
 * <p>
 * 给你一个链表的头节点 head 。<p>
 * 移除每个右侧有一个更大数值的节点。<p>
 * 返回修改后链表的头节点 head 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：head = [5,2,13,3,8]<p>
 * 输出：[13,8]<p>
 * 解释：需要移除的节点是 5 ，2 和 3 。<p>
 * - 节点 13 在节点 5 右侧。<p>
 * - 节点 13 在节点 2 右侧。<p>
 * - 节点 8 在节点 3 右侧。<p>
 * <p>
 * 示例 2：<p>
 * 输入：head = [1,1,1,1]<p>
 * 输出：[1,1,1,1]<p>
 * 解释：每个节点的值都是 1 ，所以没有需要移除的节点。<p>
 * <p>
 * 提示：<p>
 * 给定列表中的节点数目在范围 [1, 10^5] 内<p>
 * 1 <= Node.val <= 10^5<p>
 */
public class LeetCode2487 {

    @Test
    public void test01() {
        ListNode head = new ListNode(5, new ListNode(2, new ListNode(13, new ListNode(3, new ListNode(8)))));
//        ListNode head = new ListNode(1, new ListNode(1, new ListNode(1, new ListNode(1))));
        ListNode node = new Solution().removeNodes(head);
        System.out.println(node);
    }
}

class Solution {
    public ListNode removeNodes(ListNode head) {
        // 当前节点后方存在更大的节点，则移除当前节点
        // 所有元素全部从大到小的解决办法：先遍历链表，然后把不是从大到小排序的节点全部删除，最后重新生成一条链表返回
        ListNode node = head;
        Stack<ListNode> stack = new Stack<>();
        while (node != null) {
            // 将栈中小于当前节点的值去除
            while (!stack.empty() && node.val > stack.peek().val) {
                stack.pop();
            }
            if (stack.empty()) {
                // 当前栈空，说明当前节点是目前遍历到的最大节点
                head = node;
            } else {
                // 栈不为空，头结点的后续节点
                stack.peek().next = node;
            }
            // 当前节点入栈
            stack.push(node);
            // 迭代下一个节点
            node = node.next;
        }
        return head;
        // 超时
//        int cur = head.val;
//        ListNode node = head;
//        while (node.next != null) {
//            node = node.next;
//            while (cur < node.val) {
//                // 去除 cur 节点
//                head = head.next;
//                cur = head.val;
//            }
//        }
//        if (head.next != null) {
//            head.next = removeNodes(head.next);
//        }
//        return head;
    }
}

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
